{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Two City Scheduling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: twoCitySchedCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两地调度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>公司计划面试 <code>2n</code> 人。给你一个数组 <code>costs</code> ，其中 <code>costs[i] = [aCost<sub>i</sub>, bCost<sub>i</sub>]</code> 。第 <code>i</code> 人飞往 <code>a</code> 市的费用为 <code>aCost<sub>i</sub></code> ，飞往 <code>b</code> 市的费用为 <code>bCost<sub>i</sub></code> 。</p>\n",
    "\n",
    "<p>返回将每个人都飞到 <code>a</code> 、<code>b</code> 中某座城市的最低费用，要求每个城市都有 <code>n</code> 人抵达<strong>。</strong></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>costs = [[10,20],[30,200],[400,50],[30,20]]\n",
    "<strong>输出：</strong>110\n",
    "<strong>解释：</strong>\n",
    "第一个人去 a 市，费用为 10。\n",
    "第二个人去 a 市，费用为 30。\n",
    "第三个人去 b 市，费用为 50。\n",
    "第四个人去 b 市，费用为 20。\n",
    "\n",
    "最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]\n",
    "<strong>输出：</strong>1859\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]\n",
    "<strong>输出：</strong>3086\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 * n == costs.length</code></li>\n",
    "\t<li><code>2 <= costs.length <= 100</code></li>\n",
    "\t<li><code>costs.length</code> 为偶数</li>\n",
    "\t<li><code>1 <= aCost<sub>i</sub>, bCost<sub>i</sub> <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [two-city-scheduling](https://leetcode.cn/problems/two-city-scheduling/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [two-city-scheduling](https://leetcode.cn/problems/two-city-scheduling/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[10,20],[30,200],[400,50],[30,20]]', '[[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]', '[[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import itemgetter\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        gaps = [(abs(x[0] - x[1]), sum(x), x) for x in costs]\n",
    "        gaps = sorted(gaps, key=itemgetter(0, 1), reverse=True)\n",
    "        \n",
    "        a = b = 0\n",
    "        minSum = 0\n",
    "        N = len(costs)/2\n",
    "        for i, (gap, _, x) in enumerate(gaps):\n",
    "            if a < N and b < N:\n",
    "                if x[0] < x[1]:\n",
    "                    a += 1\n",
    "                    minSum += x[0]\n",
    "                else:\n",
    "                    b += 1\n",
    "                    minSum += x[1]\n",
    "            elif a == N:\n",
    "                b += 1\n",
    "                minSum += x[1]\n",
    "            else:\n",
    "                a += 1\n",
    "                minSum += x[0]\n",
    "                \n",
    "        return minSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        :type costs: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        total_cost = 0\n",
    "        total_diff = []\n",
    "        for i in range(len(costs)):\n",
    "            total_cost += costs[i][1]\n",
    "            diff = costs[i][0] - costs[i][1]\n",
    "            total_diff.append(diff)\n",
    "        total_diff.sort()\n",
    "        half_reduced = total_diff[:len(costs)//2]\n",
    "        total_cost += sum(half_reduced)\n",
    "        return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs):\n",
    "        costs.sort(key = lambda x: x[0] - x[1])\n",
    "        costa = sum(i for i,_ in costs[:len(costs)//2])\n",
    "        costb = sum(i for _,i in costs[len(costs)//2:])\n",
    "        return costa + costb\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        suma = 0\n",
    "        b = [0]*n\n",
    "        for i in range(n):\n",
    "            suma += costs[i][0]\n",
    "            b[i] = costs[i][1] - costs[i][0]\n",
    "        b.sort()\n",
    "        return suma + sum(b[0:n//2])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        # 根据每个人选择 a 城市和 b 城市的费用差值进行排序\n",
    "        sorted_array = sorted(costs, key=lambda x: x[0] - x[1])\n",
    "\n",
    "        n = len(costs) // 2\n",
    "        total_cost = 0\n",
    "\n",
    "        # 前 n 个人飞往 a 城市，其余人飞往 b 城市\n",
    "        for i in range(n):\n",
    "            total_cost += sorted_array[i][0]\n",
    "\n",
    "        for i in range(n, len(costs)):\n",
    "            total_cost += sorted_array[i][1]\n",
    "\n",
    "        return total_cost\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        tmp=[[x[0]-x[1],x[0],x[1]] for x in costs]\n",
    "        tmp=sorted(tmp,key=lambda x:x[0])\n",
    "        n=len(costs)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if i<n//2:\n",
    "                res+=tmp[i][1]\n",
    "            else:\n",
    "                res+=tmp[i][2]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        ans, n = 0, len(costs) // 2\n",
    "        pq = []\n",
    "        for ca, cb in costs[:n]:\n",
    "            ans += ca\n",
    "            heappush(pq, ca - cb)\n",
    "        for ca, cb in costs[n:]:\n",
    "            ans += ca\n",
    "            heappushpop(pq, ca - cb)\n",
    "        return ans - sum(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 摘抄自题解：https://leetcode.cn/problems/two-city-scheduling/solutions/3602/er-cha-shu-de-chui-xu-bian-li-by-leetcode/\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda row: row[0] - row[1])\n",
    "        total, n = 0, costs.__len__() // 2\n",
    "        for i in range(n):\n",
    "            total += (costs[i][0] + costs[i+n][1])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        ans, n = 0, len(costs)\n",
    "        dc = [cb - ca for ca, cb in costs]\n",
    "        def helper(l, r):\n",
    "            i = random.randint(l, r)\n",
    "            pivot = dc[i]\n",
    "            dc[i], dc[r] = dc[r], dc[i]\n",
    "\n",
    "            i = l\n",
    "            for j in range(l, r+1):\n",
    "                if dc[j] < pivot:\n",
    "                    dc[i], dc[j] = dc[j], dc[i]\n",
    "                    i += 1\n",
    "            dc[i], dc[r] = dc[r], dc[i]\n",
    "            if i > n // 2:\n",
    "                helper(l, i-1)\n",
    "            if i < n // 2 - 1:\n",
    "                helper(i+1, r)\n",
    "\n",
    "        helper(0, n-1)\n",
    "        return sum(x[0] for x in costs) + sum(dc[:n//2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key= lambda x:-abs(x[0]-x[1]))\n",
    "        left=0\n",
    "        right=0\n",
    "        n=len(costs)\n",
    "        total=0\n",
    "        for i in range(n):\n",
    "            if (costs[i][0]<costs[i][1] and left <n//2) or right>=n//2:\n",
    "                left +=1\n",
    "                total +=costs[i][0]\n",
    "            else:\n",
    "                right +=1\n",
    "                total +=costs[i][1]\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        # 首先全部去a地的费用\n",
    "        ans = sum(a for a, b in costs)\n",
    "        # 每个人去b地与去a地的差价\n",
    "        diff = [b-a for a, b in costs]\n",
    "        # 从小到大原地排序\n",
    "        diff.sort()\n",
    "\n",
    "        ans += sum(diff[:len(costs)//2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        #贪心+计算贡献\n",
    "        #计算差值最小\n",
    "        n=len(costs)//2\n",
    "        delta=[]\n",
    "        for a,b in costs:\n",
    "            delta.append(b-a)\n",
    "        delta.sort()\n",
    "        ans=sum([i[0] for i in costs])\n",
    "        for i in range(n):\n",
    "            ans+=delta[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "            # 计算费用差值，并将人员按照费用差值排序\n",
    "            cost_diff = [(i, aCost - bCost) for i, (aCost, bCost) in enumerate(costs)]\n",
    "            cost_diff.sort(key=lambda x: x[1])\n",
    "\n",
    "            total_cost = 0\n",
    "            n = len(costs) // 2\n",
    "\n",
    "            # 前n个人去a城市，后n个人去b城市\n",
    "            for i in range(n):\n",
    "                total_cost += costs[cost_diff[i][0]][0]\n",
    "\n",
    "            for i in range(n, len(costs)):\n",
    "                total_cost += costs[cost_diff[i][0]][1]\n",
    "\n",
    "            return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x : x[0] - x[1])\n",
    "        ans = 0\n",
    "        n = len(costs) // 2\n",
    "        for i in range(n):\n",
    "            ans += costs[i][0]\n",
    "        for i in range(n,2*n):\n",
    "            ans += costs[i][1]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x: x[0] - x[1])\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        n = len(costs) // 2\n",
    "\n",
    "        for i in range(n):\n",
    "            res += costs[i][0] + costs[i + n][1]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key = lambda x:x[0]-x[1])\n",
    "        n = len(costs)>>1\n",
    "        return sum(map(lambda x:x[0],costs[:n])) + sum(map(lambda x:x[1],costs[n:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        N = len(costs)\n",
    "        arr = [0 for i in range(N)]\n",
    "        sumRes = 0\n",
    "        for i in range(N):\n",
    "            arr[i] = costs[i][1] - costs[i][0]\n",
    "            sumRes += costs[i][0]\n",
    "            \n",
    "        # 从小到大排序\n",
    "        arr.sort()\n",
    "\n",
    "        M = N >> 1\n",
    "        # 让去B收益最小的M个司机，去B\n",
    "        for i in range(M):\n",
    "            sumRes += arr[i]\n",
    "        return sumRes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "            # 计算费用差值，并将人员按照费用差值排序\n",
    "            cost_diff = [(i, aCost - bCost) for i, (aCost, bCost) in enumerate(costs)]\n",
    "            cost_diff.sort(key=lambda x: x[1])\n",
    "\n",
    "            total_cost = 0\n",
    "            n = len(costs) // 2\n",
    "\n",
    "            # 前n个人去a城市，后n个人去b城市\n",
    "            for i in range(n):\n",
    "                total_cost += costs[cost_diff[i][0]][0]\n",
    "\n",
    "            for i in range(n, len(costs)):\n",
    "                total_cost += costs[cost_diff[i][0]][1]\n",
    "\n",
    "            return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        costs.sort(key= lambda x : x[0] - x[1])\n",
    "\n",
    "        END = len(costs)\n",
    "        ptr1 = 0\n",
    "        ptr2 = END // 2\n",
    "        while ptr2 < END:\n",
    "            ans += costs[ptr1][0] + costs[ptr2][1]\n",
    "            \n",
    "            ptr2 += 1\n",
    "            ptr1 += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        sort_costs = sorted(costs, key = lambda x: x[0] - x[1])\n",
    "        n = len(costs) // 2\n",
    "        total_cost = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            total_cost += sort_costs[i][0]\n",
    "\n",
    "        for j in range(n, len(costs)):\n",
    "            total_cost += sort_costs[j][1]\n",
    "\n",
    "        return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        # 按照A和B费用差距的绝对值来降序排序\n",
    "        # 差距越大，则先选，然后每次选择费用小的。这样子才能省下更多钱\n",
    "        n = len(costs)//2\n",
    "        res = 0\n",
    "        remainA,remainB = n,n\n",
    "        costs.sort(key=lambda x:(abs(x[0]-x[1])), reverse=True)\n",
    "        idx = 0\n",
    "        while remainA>0 and remainB>0:\n",
    "            cur = costs[idx]\n",
    "            if cur[0]<cur[1]:\n",
    "                remainA -= 1\n",
    "                res+=cur[0]\n",
    "            else:\n",
    "                remainB -= 1\n",
    "                res+=cur[1]\n",
    "            idx+=1\n",
    "        \n",
    "        while remainA>0:\n",
    "            res += costs[idx][0]\n",
    "            idx+=1\n",
    "            remainA -= 1\n",
    "        while remainB>0:\n",
    "            res += costs[idx][1]\n",
    "            idx+=1\n",
    "            remainB -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        acost = []\n",
    "        bcost = []\n",
    "        amoney = 0\n",
    "        bmoney = 0\n",
    "        for i in range(n):\n",
    "            if costs[i][0]<costs[i][1]:\n",
    "                acost.append([costs[i][0],costs[i][1]])\n",
    "                amoney += costs[i][0]\n",
    "            else:\n",
    "                bcost.append([costs[i][1],costs[i][0]])\n",
    "                bmoney += costs[i][1]\n",
    "        money = amoney+bmoney\n",
    "        \n",
    "        an = len(acost)\n",
    "        bn = len(bcost)\n",
    "        if an>bn:\n",
    "            an,bn = bn,an\n",
    "            acost,bcost = bcost,acost\n",
    "        \n",
    "        bcost.sort(key = lambda x: x[1]-x[0])\n",
    "        for k in range(int(n/2)-an):\n",
    "            money = money-bcost[k][0]+bcost[k][1]\n",
    "        return money\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        # 先按照最低费用分为两队人\n",
    "        # 再看人多的那一队\n",
    "        # 从那一队中选择差值最小的人移到另一边（贪心）\n",
    "        A = []\n",
    "        B = []\n",
    "        ans = 0\n",
    "        for i, (a, b) in enumerate(costs):\n",
    "            if a > b:\n",
    "                ans += b\n",
    "                heappush(A, a - b)\n",
    "            else:\n",
    "                ans += a\n",
    "                heappush(B, b - a)\n",
    "        diff = (len(A) - len(B)) >> 1\n",
    "        if diff == 0:\n",
    "            return ans\n",
    "        if diff > 0:    # A比B多\n",
    "            for _ in range(diff):\n",
    "                ans += heappop(A)\n",
    "        else:    # B比A多\n",
    "            for _ in range(-diff):\n",
    "                ans += heappop(B)\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key = lambda x : x[0] - x[1])\n",
    "        \n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "        for i in range(n):\n",
    "            total += costs[i][0] + costs[i + n][1]\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs):\n",
    "        #从代价高的开始选，选到某地满人为止\n",
    "        n = len(costs) // 2\n",
    "        cost_dict = {}\n",
    "        for man in costs:\n",
    "            cost = abs(man[0] - man[1])\n",
    "            cost_dict[cost] = cost_dict.get(cost, []) + [man]\n",
    "\n",
    "        allcosts = sorted(cost_dict.keys(), reverse = True)\n",
    "        acnt, bcnt, ret = 0, 0, 0\n",
    "        flag = -1\n",
    "        for cost in allcosts:\n",
    "            for man in cost_dict[cost]:\n",
    "                if flag != -1:\n",
    "                    ret += man[flag]\n",
    "                elif man[0] > man[1]:\n",
    "                    bcnt += 1\n",
    "                    ret += man[1]\n",
    "                    if bcnt == n:\n",
    "                        flag = 0\n",
    "                else:\n",
    "                    acnt += 1\n",
    "                    ret += man[0]\n",
    "                    if acnt == n:\n",
    "                        flag = 1\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x: x[0] - x[1])\n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "        for i in range(n):\n",
    "            total += costs[i][0] + costs[n + i][1]\n",
    "        return total\n",
    "\n",
    "\n",
    "# 公司首先将这 2N 个人全都安排飞往 B 市，再选出 N 个人改变它们的行程，让他们飞往 A 市。\n",
    "# 如果选择改变一个人的行程，那么公司将会额外付出 price_A - price_B 的费用，这个费用可正可负。\n",
    "# 因此最优的方案是，选出 price_A - price_B 最小的 N 个人，让他们飞往 A 市，其余人飞往 B 市。\n",
    "\n",
    "\n",
    "# 安排原本要去 B 市的人 转而去A市。 那么priceA就是花费的成本， priceB就是节约下来的钱。\n",
    "# 花费越少越好， 节约的越多越好。所以priceA-priceB越小越好。最小的一半人去A， 剩下的去B\n",
    "# class Solution:\n",
    "#     def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "#         costs.sort(key=lambda x: x[0] - x[1])\n",
    "#         total = 0\n",
    "#         n = len(costs) // 2\n",
    "#         for i in range(n):\n",
    "#             # total += A城市 + B城市\n",
    "#             total += costs[i][0] + costs[i + n][1]\n",
    "#         return total\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x: x[0] - x[1])\n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "        for i in range(n):\n",
    "            total += costs[i][0] + costs[i+n][1]\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        #先假设将所有人都调度到较小cost的城市\n",
    "        a_total = []\n",
    "        b_total = []\n",
    "        for c in costs:\n",
    "            if c[0] < c[1]:\n",
    "                a_total.append(c)\n",
    "            else:\n",
    "                b_total.append(c)\n",
    "        \n",
    "        #计算目前花费\n",
    "        cur_sum = sum([i[0] for i in a_total]) + sum([i[1] for i in b_total])\n",
    "        if len(a_total) > len(b_total):\n",
    "            gap_num = (len(a_total) - len(b_total))//2\n",
    "            a_total.sort(key=lambda x: x[1]-x[0])\n",
    "\n",
    "            #加上差额\n",
    "            cur_sum += sum([ (i[1]-i[0]) for i in a_total[:gap_num]])\n",
    "\n",
    "        if len(b_total) > len(a_total):\n",
    "            gap_num = (len(b_total) - len(a_total))//2            \n",
    "            b_total.sort(key=lambda x: x[0]-x[1])\n",
    "            #加上差额\n",
    "            cur_sum += sum([ (i[0]-i[1]) for i in b_total[:gap_num]])\n",
    "        return cur_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)//2\n",
    "        res = 0\n",
    "        remainA,remainB = n,n\n",
    "        costs.sort(key=lambda x:(abs(x[0]-x[1])), reverse=True)\n",
    "        idx = 0\n",
    "        while remainA>0 and remainB>0:\n",
    "            cur = costs[idx]\n",
    "            if cur[0]<cur[1]:\n",
    "                remainA -= 1\n",
    "                res+=cur[0]\n",
    "            else:\n",
    "                remainB -= 1\n",
    "                res+=cur[1]\n",
    "            idx+=1\n",
    "        \n",
    "        while remainA>0:\n",
    "            res += costs[idx][0]\n",
    "            idx+=1\n",
    "            remainA -= 1\n",
    "        while remainB>0:\n",
    "            res += costs[idx][1]\n",
    "            idx+=1\n",
    "            remainB -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        cost = []\n",
    "        n = len(costs)\n",
    "        for i in range(n):\n",
    "            res += costs[i][0]\n",
    "            cost.append(costs[i][1] - costs[i][0])\n",
    "        cost.sort(key=lambda x: x)\n",
    "        for i in range(n // 2):\n",
    "            res += cost[i]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x:(x[0] - x[1]))\n",
    "        return sum(a for a, _ in costs[:len(costs)//2]) + sum(b for _, b in costs[len(costs)//2:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x:x[1] - x[0])\n",
    "        n = len(costs)\n",
    "        mid = n // 2\n",
    "        count = 0\n",
    "        for i in range(mid):\n",
    "            count += costs[i][1]\n",
    "        for j in range(mid, n):\n",
    "            count += costs[j][0]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        lst, n = list(zip(*sorted(costs, key = lambda x : x[0] - x[1]))), len(costs) >> 1\n",
    "        return sum(lst[0][:n]) + sum(lst[1][-n:])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n=len(costs)\n",
    "        ls=[]\n",
    "        ret=0\n",
    "        for i in range(n):\n",
    "            ls.append(costs[i][1]-costs[i][0])\n",
    "            ret+=costs[i][0]\n",
    "        ls.sort()\n",
    "        for i in range(n//2):\n",
    "            ret+=ls[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key = lambda x : x[0] - x[1])\n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "        for i in range(n):\n",
    "            total += costs[i][0] + costs[i + n][1]\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "      \n",
    "        costs.sort(key = lambda x : x[0] - x[1])\n",
    "        \n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "      \n",
    "        for i in range(n):\n",
    "            total += costs[i][0] + costs[i + n][1]\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)//2\n",
    "        costs.sort(key = lambda x:x[0]-x[1])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += costs[i][0]\n",
    "            ans += costs[i+n][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        costs.sort(key = lambda x: x[0] - x[1])\n",
    "\n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            total += costs[i][0] + costs[i + n][1]\n",
    "\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        a=0\n",
    "        b=0\n",
    "        ans=0\n",
    "        arr=[]\n",
    "        n=len(costs)//2\n",
    "        for i,(costa,costb) in enumerate(costs):\n",
    "            arr.append([abs(costa-costb),costa,costb])\n",
    "        arr.sort(key=lambda x:-x[0])\n",
    "        print(arr)\n",
    "        for i,(dif,costa,costb) in enumerate(arr):\n",
    "            \n",
    "            if a==n:\n",
    "                ans+=costb\n",
    "                b+=1\n",
    "            elif b==n:\n",
    "                ans+=costa\n",
    "                a+=1\n",
    "            else:\n",
    "                if costa>=costb:\n",
    "                    b+=1\n",
    "                    ans+=costb\n",
    "                else:\n",
    "                    a+=1\n",
    "                    ans+=costa\n",
    "            print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        # 把两个数字合成一个来排序\n",
    "        n = len(costs)\n",
    "        k = n // 2\n",
    "        costs.sort(key=lambda x: x[0]-x[1])\n",
    "        a_costs = sum(i for i, _ in costs[:k])\n",
    "        b_costs = sum(i for _, i in costs[k:])\n",
    "        return a_costs + b_costs\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        #贪心+计算贡献\n",
    "        n=len(costs)//2\n",
    "        delta=[]\n",
    "        for i,(a,b) in enumerate(costs):\n",
    "            delta.append((b-a,i))\n",
    "        delta.sort()\n",
    "        ans=0\n",
    "        for k in range(2*n):\n",
    "            if k<n:\n",
    "                ans+=costs[delta[k][1]][0]+delta[k][0]\n",
    "            else:\n",
    "                ans+=costs[delta[k][1]][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x:x[0]-x[1])\n",
    "        n = len(costs)//2\n",
    "        return sum(i[0] for i in costs[:n])+sum(i[1] for i in costs[n:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key = lambda x :x[0] - x[1])\n",
    "        n = len(costs)//2\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += costs[i][0] + costs[i+n][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        #贪心+计算贡献\n",
    "        #计算差值最小\n",
    "        n=len(costs)//2\n",
    "        delta=[]\n",
    "        for i,(a,b) in enumerate(costs):\n",
    "            delta.append((b-a,i))\n",
    "        delta.sort()\n",
    "        ans=0\n",
    "        for k in range(2*n):\n",
    "            if k<n:\n",
    "                ans+=costs[delta[k][1]][0]+delta[k][0]\n",
    "            else:\n",
    "                ans+=costs[delta[k][1]][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        ans=[]\n",
    "        k=0\n",
    "        for i,j in costs:\n",
    "            ans.append([i-j,k])\n",
    "            k+=1\n",
    "        B=sorted(ans,key=lambda x:x[0])\n",
    "        res=0\n",
    "        l=0\n",
    "        while l<len(B)//2:\n",
    "            [k1,k2]=B[l]\n",
    "            res+=costs[k2][0]\n",
    "            l+=1\n",
    "        for i in range(l,len(B)):\n",
    "            [k1,k2]=B[i]\n",
    "            res+=costs[k2][1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x : x[0] - x[1])\n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "        for i in range(n):\n",
    "            total += costs[i][0] + costs[i+n][1]\n",
    "        return total\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        cost_c = [[index, a - b] for index, (a, b) in enumerate(costs) ]\n",
    "        cost_c.sort(key=lambda x:x[1])\n",
    "        res = 0\n",
    "        n = len(costs) // 2\n",
    "        for i in range(n):\n",
    "            res += costs[cost_c[i][0]][0] + costs[cost_c[i + n][0]][1]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "\t\tdis = []\n",
    "\t\tvalue = 0\n",
    "\t\tfor index, data in enumerate(costs):\n",
    "\t\t\ttemp = data[0] - data[1]\n",
    "\t\t\tdis.append((temp, index))\n",
    "\t\tfinal = sorted(dis, key=lambda di: (di[0]))\n",
    "\t\tfor index, data in enumerate(final):\n",
    "\t\t\tif index < int(len(dis) / 2):\n",
    "\t\t\t\tvalue += costs[data[1]][0]\n",
    "\t\t\telse:\n",
    "\t\t\t\tvalue += costs[data[1]][1]\n",
    "\t\treturn value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        m = len(costs)\n",
    "        n = m // 2\n",
    "\n",
    "        costs.sort(key=lambda x:x[0]-x[1])\n",
    "        return sum(a for a, b in costs[:n]) + sum(b for a, b in costs[n:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key = lambda x:(x[0]-x[1]))\n",
    "        print(costs)\n",
    "        result = 0\n",
    "        result+=sum(i[0] for i in costs[:len(costs)//2])\n",
    "        result+=sum(i[1] for i in costs[len(costs)//2:])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x : x[0] - x[1])\n",
    "\n",
    "        res = 0\n",
    "        n = len(costs) // 2\n",
    "\n",
    "        for i in range(n):\n",
    "            res += costs[i][0] + costs[i + n][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        costs.sort(key = lambda x: x[0] - x[1])\n",
    "\n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            total += costs[i][0] + costs[i + n][1]\n",
    "\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        # Sort by a gain which company has \n",
    "        # by sending a person to city A and not to city B\n",
    "        costs.sort(key = lambda x : x[0] - x[1])\n",
    "        \n",
    "        total = 0\n",
    "        n = len(costs) // 2\n",
    "        # To optimize the company expenses,\n",
    "        # send the first n persons to the city A\n",
    "        # and the others to the city B\n",
    "        for i in range(n):\n",
    "            total += costs[i][0] + costs[i + n][1]\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key = lambda x: x[0]-x[1])\n",
    "        res = 0\n",
    "        n = len(costs) // 2\n",
    "        for i in range(n):\n",
    "            res += costs[i][0] + costs[i+n][1]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # Sort by a gain which company has \n",
    "        # # by sending a person to city A and not to city B\n",
    "        # costs.sort(key = lambda x : x[0] - x[1])\n",
    "        \n",
    "        # total = 0\n",
    "        # n = len(costs) // 2\n",
    "        # # To optimize the company expenses,\n",
    "        # # send the first n persons to the city A\n",
    "        # # and the others to the city B\n",
    "        # for i in range(n):\n",
    "        #     total += costs[i][0] + costs[i + n][1]\n",
    "        # return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        costs.sort(key= lambda x : x[0] - x[1])\n",
    "        print(costs)\n",
    "        cnt = 0\n",
    "        end = len(costs) // 2\n",
    "        ic = iter(costs)\n",
    "        for a, b in ic:\n",
    "            ans += a\n",
    "            cnt += 1\n",
    "            if cnt == end: break\n",
    "        cnt = 0\n",
    "        for a, b in ic:\n",
    "            ans += b\n",
    "            cnt += 1\n",
    "            if cnt == end: break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n=len(costs)//2\n",
    "        diff = []\n",
    "        res = 0\n",
    "        for i in range(2*n):\n",
    "            acost,bcost = costs[i]\n",
    "            costs[i].append(acost-bcost)\n",
    "        costs.sort(key = lambda x:x[2])\n",
    "        print(costs)\n",
    "        for i in range(n):\n",
    "            res += costs[i][0]\n",
    "        for i in range(n,2*n):\n",
    "            res += costs[i][1]\n",
    "        \n",
    "        return res\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key = lambda x: -abs(x[0] - x[1]))\n",
    "        point_a, point_b = 0, 0\n",
    "        n = len(costs) // 2\n",
    "        ans = 0\n",
    "        for cost in costs:\n",
    "            if point_a == n:\n",
    "                ans += cost[1]\n",
    "            elif point_b == n:\n",
    "                ans += cost[0]\n",
    "            elif cost[0] < cost[1]:\n",
    "                ans += cost[0]\n",
    "                point_a += 1\n",
    "            else:\n",
    "                ans += cost[1]\n",
    "                point_b += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        diff = [[abs(a-b),a,b] for a,b in costs]\n",
    "        diff.sort(reverse = True)\n",
    "        n = len(costs)\n",
    "        A, B, result = 0, 0, 0\n",
    "        for i in range(len(diff)):\n",
    "            if A == n/2: \n",
    "                B, result = B + 1, result + diff[i][2]\n",
    "            elif B == n/2: \n",
    "                A, result = A + 1, result + diff[i][1]\n",
    "            elif A < n/2 and B < n/2 and diff[i][1] < diff[i][2]:\n",
    "                A, result = A + 1, result + diff[i][1]\n",
    "            else: \n",
    "                B, result = B + 1, result + diff[i][2]\n",
    "        return result\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        ans = sum(b for _, b in costs)\n",
    "        costs.sort(key= lambda x : x[0] - x[1])\n",
    "        print(costs)\n",
    "        for a, b in costs[:len(costs) // 2]:\n",
    "            ans -= b\n",
    "            ans += a\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs.sort(key=lambda x: x[1]-x[0])\n",
    "        total=0\n",
    "        print(costs)\n",
    "        for i in range(len(costs)//2):\n",
    "            total+=costs[i][1]\n",
    "        for j in range(len(costs)//2,len(costs)):\n",
    "            total+=costs[j][0]\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "\n",
    "        #1.让所有人都去a地，计算总开销\n",
    "        #2.在这些人里2N，若最初分出N个人去b地，则公司将少花费a-b元\n",
    "        #3.原问题变为如何用最少的开销让a地的人区b地\n",
    "        #4.总费用=min(所有人去a地的费用-公司花的冤枉钱)\n",
    "\n",
    "        cost_dis = list()\n",
    "        N = len(costs)\n",
    "        total_costs = 0\n",
    "        for i in range(N):\n",
    "            cost_dis.append(costs[i][0] - costs[i][1])\n",
    "            total_costs += costs[i][0]\n",
    "        cost_dis.sort(reverse=True)\n",
    "        return total_costs - sum(cost_dis[0:N//2])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\r\n",
    "        costs.sort(key=lambda x: x[0] - x[1])\r\n",
    "        n = len(costs) // 2\r\n",
    "        return sum(x[0] for x in costs[:n]) + sum(x[1] for x in costs[n:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        diff = []\n",
    "        Len = len(costs) // 2\n",
    "        for a, b in costs:\n",
    "            res += a\n",
    "            tmp = b - a\n",
    "            diff.append(tmp)\n",
    "        \n",
    "        diff.sort()\n",
    "        i = 0\n",
    "        while Len > 0:\n",
    "            res += diff[i]\n",
    "            i += 1\n",
    "            Len -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        ans = sum(b for _, b in costs)\n",
    "        costs.sort(key= lambda x : x[0] - x[1])\n",
    "        print(costs)\n",
    "        cnt = 0\n",
    "        end = len(costs) // 2\n",
    "\n",
    "        for a, b in costs:\n",
    "            ans -= b\n",
    "            ans += a\n",
    "            cnt += 1\n",
    "            if cnt == end: break\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        costs = sorted(costs, key = lambda x : x[0] - x[1])\n",
    "        cost = 0\n",
    "        for i,n in enumerate(costs):\n",
    "            if i < len(costs) / 2:\n",
    "                cost += n[0]\n",
    "            else:\n",
    "                cost += n[1]\n",
    "        return cost\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "\n",
    "        n2 = len(costs)\n",
    "        n = n2//2\n",
    "\n",
    "        dp = [[float(\"inf\")]*(n+1) for _ in range(n2)]\n",
    "\n",
    "        dp[0][1] = costs[0][0]\n",
    "        dp[0][0] = costs[0][1]\n",
    "\n",
    "        for i in range(1,n2):\n",
    "            for j in range(min(i+1,n)+1):\n",
    "                if j==0:\n",
    "                    dp[i][j] = dp[i-1][j]+costs[i][1]\n",
    "                    continue \n",
    "                \n",
    "                dp[i][j] = min(dp[i-1][j]+costs[i][1], dp[i-1][j-1]+costs[i][0])\n",
    "        \n",
    "        return dp[n2-1][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        dp[i][j]表示前i个人，有j个去a市的最小费用\n",
    "        dp[i][j] = min(dp[i-1][j]+cost[i][1], dp[i-1][j-1]+costs[i-1][0])\n",
    "        dp[0][0] = 0, dp[0][j] = float('inf')\n",
    "        \"\"\"\n",
    "        n = len(costs) // 2\n",
    "        dp = [[float('inf')]*(n+1) for _ in range(2*n+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, 2*n+1):\n",
    "            for j in range(n+1):\n",
    "                dp[i][j] = dp[i-1][j] + costs[i-1][1]\n",
    "                if j > 0:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+costs[i-1][0])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n = int(len(costs)/2)\n",
    "        costs = sorted(costs, key=lambda x:-abs(x[0]-x[1]))\n",
    "        print(n,costs)\n",
    "        ans = 0\n",
    "        countA,countB = 0,0\n",
    "        for i in range(2*n):\n",
    "            if countA < n and countB < n:\n",
    "                if costs[i][0] < costs[i][1]:\n",
    "                    countA += 1\n",
    "                    tmp = costs[i][0]\n",
    "                else:\n",
    "                    countB += 1\n",
    "                    tmp = costs[i][1]\n",
    "            elif countA < n:\n",
    "                tmp = costs[i][0]\n",
    "                countA += 1\n",
    "            elif countB < n:\n",
    "                tmp = costs[i][1]\n",
    "                countB += 1\n",
    "            ans += tmp\n",
    "            print(i,countA, countB, tmp)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n =  len(costs) // 2\n",
    "        costs.sort()\n",
    "        ans = 0\n",
    "        sl = SortedList()\n",
    "        for i in range(n):\n",
    "            ans += costs[i][0]\n",
    "            sl.add(costs[i][1] - costs[i][0])\n",
    "        for i in range(n, 2 * n):\n",
    "            if costs[i][0] + sl[0] < costs[i][1]:\n",
    "                ans += costs[i][0] + sl[0]\n",
    "                sl.discard(sl[0])\n",
    "                sl.add(costs[i][1] - costs[i][0])\n",
    "            else:\n",
    "                ans += costs[i][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(costs) // 2\n",
    "        '''\n",
    "        dp[i][j]:min cost from 0 - i and get j people to A\n",
    "        dp[i][j]\n",
    "        1. dp[i - 1][j - 1] + cost[i - 1][0]\n",
    "        2. dp[i - 1][j] + cost[i - 1][1]\n",
    "        '''\n",
    "        dp = [[inf] * (n + 1) for i in range(2 * n + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, 2 * n + 1):\n",
    "            for j in range(n + 1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i - 1][j] + costs[i - 1][1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0], dp[i - 1][j] + costs[i - 1][1])\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        dp = [[float('inf')] * (n//2+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0 \n",
    "        for i in range(1, n+1):\n",
    "            for j in range(n//2+1):\n",
    "                dp[i][j] = dp[i-1][j] + costs[i-1][1]\n",
    "                if j > 0:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + costs[i-1][0])\n",
    "        return dp[n][n//2]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs) // 2\n",
    "        dp = [[float(\"inf\")]*(n+1) for _ in range(2*n+1)]\n",
    "\n",
    "        dp[1][0] = costs[0][1]\n",
    "        dp[1][1] = costs[0][0]\n",
    "\n",
    "        for i in range(2,2*n+1):\n",
    "            for k in range(min(i+1,n+1)):\n",
    "                dp[i][k] = min(dp[i-1][k-1]+costs[i-1][0], dp[i-1][k]+costs[i-1][1])\n",
    "        return dp[2*n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        dp = [[[float('inf')] * (n//2+1) for _ in range(2)] for _ in range(n+1)]\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][1][0] = 0 \n",
    "        for i in range(1, n+1):\n",
    "            for j in range( n//2+1):\n",
    "                dp[i][0][j] = min(dp[i-1][0][j] + costs[i-1][1], dp[i-1][1][j] + costs[i-1][1]) \n",
    "                if j > 0:\n",
    "                    dp[i][1][j] = min(dp[i-1][0][j-1] + costs[i-1][0], dp[i-1][1][j-1] + costs[i-1][0])\n",
    "        return min(dp[n][0][n//2], dp[n][1][n//2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoCitySchedCost(self, costs: List[List[int]]) -> int:\n",
    "        n=len(costs)\n",
    "        BIG=10**10\n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if abs(k)>(n-i):return BIG\n",
    "            if i==n:\n",
    "                if k==0:return 0\n",
    "                return BIG\n",
    "            a,b=costs[i]\n",
    "            return min(a+dfs(i+1,k-1),b+dfs(i+1,k+1))\n",
    "        return dfs(0,0)\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
